/*
*	ID : pallab81
* 	PROG : REPEATS
* 	LANG : C++
* 	2012-09-01-12.29.49 Saturday
*
* 	"I have not failed, I have just found 10000 ways that won't work.
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;


#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

template<class T1>
inline void debug(T1 _x) {
    cout<<_x<<'\n';
}
template<class T1, class T2>
inline void debug(T1 _x,T2 _y) {
    cout<<_x<<' '<<_y<<'\n';
}
template<class T1, class T2, class T3>
inline void debug(T1 _x,T2 _y,T3 _z) {
    cout<<_x<<' '<<_y<<' '<<_z<<'\n';
}
template<class T1, class T2, class T3, class T4>
inline void debug(T1 _x,T2 _y,T3 _z,T4 _zz) {
    cout<<_x<<' '<<_y<<' '<<_z<<' '<<_zz<<'\n';
}
template< class T1>
inline void debug(T1 _array,int _size) {
    cout<<"[";
    for (int i=0; i<_size; ++i) {
        cout<<' '<<_array[i];
    }
    puts(" ]");
}
inline bool CI(int &_x) {
    return scanf("%d",&_x)==1;
}
inline bool CI(int &_x, int &_y) {
    return CI(_x)&&CI(_y) ;
}
inline bool CI(int &_x, int &_y, int &_z) {
    return CI(_x)&&CI(_y)&&CI(_z) ;
}
inline bool CI(int &_x, int &_y, int &_z, int &_zz) {
    return CI(_x)&&CI(_y)&&CI(_z)&&CI(_zz) ;
}
inline void wait( double seconds ) {
    double endtime = clock()+( seconds* CLOCKS_PER_SEC );
    while( clock() < endtime ) {
        ;
    }
}
#if !defined( ONLINE_JUDGE )
#define debug
#endif
const int mxn = 50010;
int ncount;
int str[mxn];
namespace suffix_array {
const int maxn=50010;
const int inf=5000000;
int w[maxn],wa[maxn],wb[maxn],wv[maxn];
int sa[maxn],rank[maxn],height[maxn];
int a[maxn],f[maxn][20],n,ft[maxn];
int cmp(int *r,int a,int b,int l) {
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m) {
    int i,j,p,*x=wa,*y=wb,*t;
    for (i=0; i<m; i++) w[i]=0;
    for (i=0; i<n; i++) w[x[i]=r[i]]++;
    for (i=1; i<m; i++) w[i]+=w[i-1];
    for (i=n-1; i>=0; i--) sa[--w[x[i]]]=i;
    for (p=1,j=1; p<n; m=p,j*=2) {
        for (p=0,i=n-j; i<n; i++) y[p++]=i;
        for (i=0; i<n; i++) if (sa[i]>=j) y[p++]=sa[i]-j;
        for (i=0; i<m; i++) w[i]=0;
        for (i=0; i<n; i++) w[wv[i]=x[y[i]]]++;
        for (i=1; i<m; i++) w[i]+=w[i-1];
        for (i=n-1; i>=0; i--) sa[--w[wv[i]]]=y[i];
        for (t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1; i<n; i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void cal(int *r,int *sa,int n) {
    int i,j,k=0;
    for (i=1; i<=n; i++) rank[sa[i]]=i;
    for (i=0; i<n; height[rank[i++]]=k)
        for (k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}
int nmin(int a,int b) {
    return a<b?a:b;
}
void rmq(int n) {
    int i,j;
    for (i=1; i<=n; i++)
        f[i][0]=height[i];
    for (j=1; j<20; j++)
        for (i=1; i+(1<<j)-1<=n; i++)
            f[i][j]=nmin(f[i][j-1],f[i+( 1<<(j-1) )][j-1]);
    return;
}
int lcp(int a,int b) {
    int x=rank[a],y=rank[b];
    if (x>y) {
        int t=x;
        x=y;
        y=t;
    }
    x++;
    int t=ft[y-x+1];
    return nmin(f[x][t],f[y-(1<<t)+1][t]);
}
void init() {
    fo(i,maxn) {
        ft[i]= (int)( ( double(log(i)) )/log(2.0) );
    }
}
}

inline void read() {
    scanf("%d\n",&ncount);
    char x;
    fo(i,ncount) {
        scanf("%c\n",&x);
        str[i]=x;
    }
}
inline void proc() {
    //fit
    str[ncount]=0;

    suffix_array::da(str,suffix_array::sa,ncount+1,128);
    suffix_array::cal(str, suffix_array::sa, ncount);
    suffix_array::rmq(ncount);

    int bst=0;
    for(int l=1; l<ncount; l++) {
        for(int i=0; i+l<ncount; i+=l) {
            int k=suffix_array::lcp(i,i+l);
            int r=k/l+1;
            int t=i-(l-k%l);
            if (t>=0&& (k%l) !=0) {
                if ( suffix_array::lcp(t,t+l)>=k) {
                    ++r;
                }
            }
            bst = max( bst, r);
        }
    }
    cout<<bst<<'\n';
}

int main() {
#if !defined ( ONLINE_JUDGE )
    freopen("in","r",stdin);
#endif

    suffix_array::init();

    int kase;
    scanf("%d\n",&kase);
    fo(i,kase) {
        read();
        proc();
    }
    return 0;
}

